package demo;

import java.util.Stack;

/**
 *    接雨水
 */
class Solution28 {
	public int trap(int[] height) {
		int max = 0;
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < height.length; i++) {
			while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
				int top = stack.pop();
				while (!stack.isEmpty() && height[top] == height[stack.peek()]) {
					stack.pop();
				}
				if (!stack.isEmpty()) {
					int tmp = height[stack.peek()];
					int h = Math.min(tmp - height[top], height[i] - height[top]);
					int w = i - 1 - stack.peek();
					max += h*w;
				}
			}
			stack.push(i);
		}
		return max;
	}
}

